public class Solution5 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null&&list2==null)
            return null;
        ListNode ret = new ListNode();
        ListNode cur = ret;
        ListNode i = list1;
        ListNode j = list2;
        while(i!=null&&j!=null){
            if(i.val <= j.val){
                ListNode node = new ListNode(i.val);
                cur.next=node;
                cur=cur.next;
                i=i.next;
            }else if(i.val> j.val){
                ListNode node = new ListNode(j.val);
                cur.next=node;
                cur=cur.next;
                j=j.next;
            }
        }
        while(i!= null){
            ListNode node = new ListNode(i.val);
            cur.next=node;
            cur=cur.next;
            i=i.next;
        }
        while(j!=null){
            ListNode node = new ListNode(j.val);
            cur.next=node;
            cur=cur.next;
            j=j.next;
        }
        return ret.next;
    }
}
